1. Field
This application relates to communication networks and, more particularly, to a method for reducing processing latency in a multi-thread packet processor with at least one re-order queue.
2. Description of the Related Art
Data communication networks may include various switches, nodes, routers, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements”. Data is communicated through the data communication network by passing protocol data units, such as frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
When a packet is received by a network element, the network element will process the packet and forward the packet on to its destination. To accelerate packet processing, a multi-thread packet processor may be used in which an execution pipeline is used to processes packets and each packet is assigned to a thread. Each thread processes a packet and has its own dedicated context, such as a program counter, link registers, address registers, data registers, local memories, etc. To increase performance, two or more execution pipelines may be used to process packets in parallel.
To prevent packets from arriving at their destination out of order, it is common for packets to be transmitted by a network element in the same order in which they are received. When a packet arrives, it is assigned to the next available thread and processed. Packets may be processed out of order, but before transmission the packets are re-ordered to restore the original order prior to transmission.
Typically, re-ordering is done using a single re-order queue. The re-order queue behaves as a First-In-First-Out (FIFO) memory. When a packet arrives, it is tagged with a unique service number, placed in the FIFO queue, and its tag is used as an index to set a busy flag in a scoreboard table. When the thread finishes processing the packet, it uses the tag to clear the busy flag in the scoreboard table. After releasing the busy flag, the thread is placed into the free thread pool to be picked up by the next packet. The re-order queue reader agent is an independent entity that constantly uses the tag from the packet at the head of the FIFO to check the scoreboard table to determine if the corresponding busy flag is cleared. Once the busy flag for the packet at the head of the FIFO has been released, the packet at the head of the FIFO queue is transmitted out and the queue read pointer is advanced to point to the next packet in the queue.
There are instances where one packet has completed processing, and is ready to be transmitted, but other packets ahead of it in the reorder queue are not yet ready to be transmitted. For example, different types of packets may have different processing requirements. However, because the packets must be transmitted in the same order in which they were received, this will cause transmission of the packet to be delayed even though the network element has finished processing that packet. Specifically, if other packets ahead of it in the queue have not completed processing, the packet that has completed processing must wait until all the other packets ahead of it in the queue finish processing before it can be transmitted. Accordingly, it would be advantageous to provide a way to accelerate transmission of packets without compromising the in-order transmission of packets from a network element.